package com.lw.leetcode.str.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 马拉车示例
 * 1960. 两个回文子字符串长度的最大乘积
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/12 16:18
 */
public class MaxProduct {

    public static void main(String[] args) {
        MaxProduct test = new MaxProduct();

        // 0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 4, 0, 1, 0, 0
        // 63
//        String str = "abacabadabacabad";

        // 63
//        String str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        // 63
        String str = Utils.getStr(100000, 'a', 'a');

        long l = test.maxProduct(str);
        System.out.println(l);
    }

    public long maxProduct(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        int[] arr = new int[length];
        int[] maxs1 = find(chars, arr);
        int m = length >> 1;
        for (int i = 0; i < m; i++) {
            int j = length - 1 - i;
            char t = chars[i];
            chars[i] = chars[j];
            chars[j] = t;
        }
        int[] maxs2 = find(chars, arr);
        long max = 0;
        for (int i = 0; i < length - 1; i++) {
            int j = length - i - 2;
            max = Math.max(max, (long) maxs1[i] * maxs2[j]);
        }
        return max;
    }

    private int[] find(char[] chars, int[] arr) {
        int length = chars.length;
        int[] maxs = new int[length];
        int last = 0;
        int m = 0;
        for (int i = 0; i < length; i++) {
            int step = 1;
            if (i < last) {
                step = arr[(m << 1) - i];
                if (i + step < last) {
                    arr[i] = step;
                    continue;
                }
                step = last - i + 1;
            }
            while (true) {
                int a = i - step;
                int b = i + step;
                if (a < 0 || b >= length || chars[a] != chars[b]) {
                    step--;
                    break;
                }
                step++;
            }
            if (last < i + step) {
                last = Math.min(length - 1, i + step);
                m = i;
            }
            arr[i] = step;
        }
        maxs[0] = 1;
        for (int i = 1; i < length; i++) {
            int max = maxs[i - 1] >> 1;
            int t = i - 1 - max;
            if (arr[t] >= max && t - max - 1 >= 0 && chars[t - max - 1] == chars[i]) {
                max += 1;
            }
            maxs[i] = (max << 1) + 1;
        }
        return maxs;
    }

}
